"""
给定一个二叉树，计算整个树的坡度。

一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

整个树的坡度就是其所有节点的坡度之和。

 

示例：

输入：
         1
       /   \
      2     3
输出：1
解释：
结点 2 的坡度: 0
结点 3 的坡度: 0
结点 1 的坡度: |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-tilt
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def __init__(self):
        self.ans = 0

    def findTilt(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.func(root)
        return self.ans

    def func(self, root: TreeNode) -> int:
        if not root:
            return 0
        left_val = self.func(root.left)
        right_val = self.func(root.right)
        self.ans += abs(left_val - right_val)
        return root.val + left_val + right_val

    def findTilt2(self, root: TreeNode) -> int:
        if not root:
            return 0

        def func(root: TreeNode):
            if not root:
                return 0
            l = func(root.left)
            r = func(root.right)
            self.ans += abs(l - r)
            return l + r + root.val

        func(root)
        return self.ans
